/*
计算给定二叉树的所有左叶子之和

    3
   / \
  9  20
    /  \
   15   7

在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24



*/

//深度优先搜索
class Solution
{
public:
    bool isLeafNode(TreeNode *node)
    {
        return !node->left && !node->right;
    }

    int dfs(TreeNode *node)
    {
        int ans = 0;
        if (node->left)
        {
            ans += isLeafNode(node->left) ? node->left->val : dfs(node->left);
        }
        if (node->right && !isLeafNode(node->right))
        {
            ans += dfs(node->right);
        }
        return ans;
    }

    int sumOfLeftLeaves(TreeNode *root)
    {
        return root ? dfs(root) : 0;
    }
};


//广度优先搜索
class Solution
{
public:
    bool isLeafNode(TreeNode *node)
    {
        return !node->left && !node->right;
    }

    int sumOfLeftLeaves(TreeNode *root)
    {
        if (!root)
        {
            return 0;
        }

        queue<TreeNode *> q;
        q.push(root);
        int ans = 0;
        while (!q.empty())
        {
            TreeNode *node = q.front();
            q.pop();
            if (node->left)
            {
                if (isLeafNode(node->left))
                {
                    ans += node->left->val;
                }
                else
                {
                    q.push(node->left);
                }
            }
            if (node->right)
            {
                if (!isLeafNode(node->right))
                {
                    q.push(node->right);
                }
            }
        }
        return ans;
    }
};
